DSC 40B – Theoretical Foundations of Data Science II
Problems tagged with "best and worst case"
Problem #005
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
Solution
\(\Theta(n)\)
Problem #006
Tags: best and worst case
What is the worst case time complexity of the function in the previous problem?
Solution
\(\Theta(n^2)\)
Problem #018
Tags: best and worst case, mergesort
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
Solution
False.
Problem #023
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum. What is this code's best case time complexity?
def index_of_maximum(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
Solution
\(\Theta(n)\)
Problem #040
Tags: best and worst case
The below code takes in an array of numbers and returns the index of the first maximum.
def foo(arr):
"""`arr` is an array with n elements."""
for i, x in enumerate(arr):
if x == max(arr):
return i
What is the worst case time complexity of the function?
Solution
\(\Theta(n^2)\)
Problem #051
Tags: best and worst case
The code below takes in an array of \(n\) numbers and checks whether there is a pair of numbers in the array which, when added together, equal the maximum element of the array.
What is the best case time complexity of this code as a function of \(n\)? State your answer using asymptotic notation.
def exists_pair_summing_to_max(arr):
n = len(arr)
maximum = max(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == maximum:
return True
return False
Solution
\(\Theta(n)\)
Problem #067
Tags: best and worst case
What is the worst case time complexity of the function in the last problem? State your answer using asymptotic notation.
Solution
\(\Theta(n^2)\)
Problem #078
Tags: best and worst case
What is the best case time complexity of the following function in terms of \(n\)?
def foo(arr):
"""`arr` is a list containing n numbers."""
previous = None
n = len(arr)
for x in arr:
if x == previous:
for i in range(n**2):
print('Equal!')
return
previous = x
Solution
\(\Theta(n)\)
Problem #084
Tags: best and worst case
True or False: the best case time complexity of mergesort is \(\Theta(n)\).
Solution
False.